{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Points You Can Obtain from Cards"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可获得的最大点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>几张卡牌<strong> 排成一行</strong>，每张卡牌都有一个对应的点数。点数由整数数组 <code>cardPoints</code> 给出。</p>\n",
    "\n",
    "<p>每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 <code>k</code> 张卡牌。</p>\n",
    "\n",
    "<p>你的点数就是你拿到手中的所有卡牌的点数之和。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>cardPoints</code> 和整数 <code>k</code>，请你返回可以获得的最大点数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cardPoints = [1,2,3,4,5,6,1], k = 3\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cardPoints = [2,2,2], k = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>无论你拿起哪两张卡牌，可获得的点数总是 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cardPoints = [9,7,7,9,7,7,9], k = 7\n",
    "<strong>输出：</strong>55\n",
    "<strong>解释：</strong>你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cardPoints = [1,1000,1], k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cardPoints = [1,79,80,1,1,1,200,1], k = 3\n",
    "<strong>输出：</strong>202\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= cardPoints.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= cardPoints[i] &lt;= 10^4</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= cardPoints.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-points-you-can-obtain-from-cards](https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-points-you-can-obtain-from-cards](https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,1]\\n3', '[2,2,2]\\n2', '[9,7,7,9,7,7,9]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values) -> int:\n",
    "        start_value = values[0]\n",
    "        location = 0\n",
    "        max_value = start_value + location\n",
    "        for i in range(1, len(values)):\n",
    "            temp_value = start_value + location + values[i] - i\n",
    "            if temp_value > max_value:\n",
    "                max_value = temp_value\n",
    "            if start_value + location < values[i] + i:\n",
    "                start_value = values[i]\n",
    "                location = i\n",
    "\n",
    "        return max_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        N = len(values)\n",
    "        p = values[0]\n",
    "        ans = 0\n",
    "        for i in range(1, N):\n",
    "            ans = max(ans, p+values[i]-i)\n",
    "            p = max(p, values[i]+i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre = values[0]\n",
    "        res = -10000\n",
    "        for i in range(1, len(values)):\n",
    "            res = max(res, values[i] + pre - 1)\n",
    "            pre = max(pre - 1, values[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre_max = values[0]\n",
    "        res = 0\n",
    "        for index in range(1, len(values)):\n",
    "            value = values[index]\n",
    "            res = max(res, value - index + pre_max)\n",
    "            if pre_max <= value+index:\n",
    "                pre_max = value+index\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        max_v = 0\n",
    "        mx = values[0]\n",
    "        for j in range(1, n):\n",
    "            max_v = max(max_v, mx + values[j] - j)\n",
    "\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        maxValue = 0\n",
    "        preMax = values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            val = preMax + values[i] - i\n",
    "            maxValue = max(maxValue, val)\n",
    "            preMax = max(values[i] + i, preMax)\n",
    "        return maxValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "      ans, dp = 0, values[0]\n",
    "      for i in range(1, len(values)):\n",
    "        dp -= 1\n",
    "        ans, dp = max(ans, dp + values[i]), max(dp, values[i])\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''给你一个正整数数组 values,其中values[i] 表示第i个观光景点的评分，并且两个景点 i和j之间的距离为j-i。\n",
    "一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，\n",
    "也就是景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。'''\n",
    "'''需要注意的是，一对景点之间的距离是个迷惑项，(values[i]+i)+(values[j]-j)才是正确的思路，\n",
    "通过一次遍历，我们可以预先取得下标为[0,j)和j的结点的分数,进而我们可以以O(N)的时间复杂度完成算法设计'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef maxScoreSightseeingPair(self, values: list[int]) -> int:\n",
    "\t\tmaxScored = values[0] + 0\n",
    "\t\tans = 0\n",
    "\t\tfor j in range(1, len(values)):\n",
    "\t\t\tans = max(ans, maxScored + values[j] - j)\n",
    "\t\t\tmaxScored = max(maxScored, values[j] + j)\n",
    "\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values) -> int:\n",
    "        # values[i] + values[j] + i - j = \n",
    "        # (values[i] + i) + (values[j] - j)\n",
    "        \n",
    "        max_value_i_plus_i = 0\n",
    "        max_score = 0\n",
    "        \n",
    "        for j, value in enumerate(values): \n",
    "            max_score = max(max_score, max_value_i_plus_i + value - j)\n",
    "            max_value_i_plus_i = max(max_value_i_plus_i, value + j)\n",
    "            \n",
    "        return max_score\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = -1\n",
    "        m1 = values[0] + 0\n",
    "        for i in range(1, len(values)):\n",
    "            res = max(res, m1 + values[i] - i)\n",
    "            m1 = max(m1, values[i] + i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        last = values[0]\n",
    "        ans = -inf\n",
    "        n = len(values)\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,values[i]-i+last)\n",
    "            last = max(last,values[i]+i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_max = values[0] + 0\n",
    "        for j in range(1, len(values)):\n",
    "            res = max(res, pre_max + values[j] - j)\n",
    "            pre_max = max(pre_max, values[j] + j)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre_max = values[0]\n",
    "        res = 0\n",
    "        for index in range(1, len(values)):\n",
    "            value = values[index]\n",
    "            res = max(res, value - index + pre_max)\n",
    "            if pre_max <= value+index:\n",
    "                pre_max = value+index\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        a, b = 0, 1\n",
    "        c = values[a] + values[b] - (b - a) # 初始化答案\n",
    "        while b < n:\n",
    "            s = values[a] + values[b] - (b - a) # 计算当前观光组合得分s\n",
    "            c = max(c, s)\n",
    "            if values[a] + a < values[b] + b: # 移动指针的条件判断\n",
    "                a = b\n",
    "                b += 1\n",
    "            else:\n",
    "                b += 1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        a = values[0]-1\n",
    "        m = values[1]+a\n",
    "\n",
    "        for i in range(2,len(values)):\n",
    "            a = max(a - 1, values[i-1]-1)\n",
    "            m = max(values[i]+a,m)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max((dp[i - 1] + values[i] - values[i - 1] - 1), values[i] + values[i - 1] - 1)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        ans, max_val = values[0], values[0]\n",
    "        for j in range(1, n):\n",
    "            ans = max(ans, max_val + values[j] - j)\n",
    "            max_val = max(max_val, values[j] + j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        left=0\n",
    "        max_=float('-inf')\n",
    "        for i in range(1,len(values)):\n",
    "            max_=max(max_,values[left]+values[i]+left-i)\n",
    "            if values[i]+i>values[left]+left:\n",
    "                left=i\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        left=values[0]\n",
    "        res=-1\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,left+values[i]-i)\n",
    "            left=max(left,values[i]+i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # (A[i] + i) + (A[j] - j)\n",
    "        if len(values) < 2:\n",
    "            return 0\n",
    "        ans = float('-inf')\n",
    "        mx = 0\n",
    "        for i in range(len(values)):\n",
    "            ans = max(ans, mx + values[i] - i)\n",
    "            mx = max(mx, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        output=float(\"-inf\")\n",
    "        pre_max=values[0]+0\n",
    "        for j in range(1,n):\n",
    "            output=max(output,pre_max+values[j]-j)\n",
    "            pre_max=max(pre_max,values[j]+j)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_i = values[0] + 0  # 初始化最大的 values[i] + i 值\n",
    "        max_score = 0  # 初始化最高得分\n",
    "        for j in range(1, len(values)):\n",
    "            # 计算可能的最高得分\n",
    "            max_score = max(max_score, max_i + values[j] - j)\n",
    "            # 更新最大的 values[i] + i 值\n",
    "            max_i = max(max_i, values[j] + j)\n",
    "        return max_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans,mx=0,values[0]\n",
    "        for j in range(1,len(values)):\n",
    "            ans=max(ans,mx+values[j]-j)\n",
    "            mx=max(mx,values[j]+j)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = values[0]\n",
    "        ans = 0\n",
    "        for j in range(1, n):\n",
    "            ans = max(ans, values[j] - j + mx)\n",
    "            mx = max(mx, values[j] + j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans, premax = 0, values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            ans = max(ans, premax + values[i] - i)\n",
    "            premax = max(premax, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 遍历\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = values[0] + 0\n",
    "        \n",
    "        for j in range(1, len(values)):\n",
    "            ans = max(ans, mx + values[j] - j)\n",
    "            # 边遍历边维护\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_score = 0\n",
    "        max_i = values[0]\n",
    "        for j in range(1, len(values)):\n",
    "            max_score = max(max_score, max_i + values[j] - j)\n",
    "            max_i = max(max_i, values[j] + j)\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        tmp = values[0]\n",
    "\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,tmp+values[i]-i)\n",
    "            tmp = max(tmp,values[i]+i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        buff = values[0] # 初始buff\n",
    "        ans = 0\n",
    "        for j in range(1, len(values)):\n",
    "        # 随着时间推移，buff的效力不断减少\n",
    "        # 初始效力为某个A[i], i < j\n",
    "        # 随时间减少的效力正好为 j - i\n",
    "        # 因此当前buff的剩余效力恰为 A[i] + i - j\n",
    "            buff -= 1\n",
    "            # 根据当前buff默默算一下自己的战斗力（战5渣..)\n",
    "            ans = max(ans, values[j] + buff)\n",
    "            # 看看当前buff剩余效力有没有刷新buff好，没有则刷新buff\n",
    "            buff = max(buff, values[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = -inf\n",
    "        for x in values:\n",
    "            ans = max(ans, pre + x)\n",
    "            pre = max(pre, x)\n",
    "            pre -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        import sortedcontainers\n",
    "        res, l = 0, sortedcontainers.SortedList()\n",
    "        for i in range(len(values)): l.add(values[i]-i)\n",
    "        for i in range(len(values)-1):\n",
    "            l.discard(values[i]-i)\n",
    "            res = max(res, values[i]+i+l[-1])\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        stack = []\n",
    "        ans = -inf\n",
    "        heappush(stack,-values[0])\n",
    "        n = len(values)\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,values[i]-i-stack[0])\n",
    "            heappush(stack,-values[i]-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        mx = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,mx+values[i]-i)\n",
    "            mx = max(mx,values[i]+i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = values[0]\n",
    "        ans = [0] * n\n",
    "        for j in range(1, n):\n",
    "            ans[j] = values[j] - j + mx\n",
    "            mx = max(mx, values[j] + j)\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_value = values[0] + values[1] - 1\n",
    "        pre_max = max(values[0]-1, values[1])\n",
    "        for i in range(2, len(values)):\n",
    "            pre_max-=1\n",
    "            max_value = max(max_value, pre_max+values[i])\n",
    "            pre_max = max(pre_max, values[i])\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        for i in range(len(values)):\n",
    "            values[i]=values[i]-i\n",
    "        res=0\n",
    "        mx=values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,mx+values[i])\n",
    "            mx=max(mx,values[i]+2*i)\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        for i in range(len(values)):\n",
    "            values[i]=values[i]-i\n",
    "        res=0\n",
    "        mx=values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,mx+values[i])\n",
    "            mx=max(mx,values[i]+2*i)\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        imax = values[0]\n",
    "        res = imax + values[1] - 1\n",
    "        for j in range(2, len(values)):\n",
    "            if (s := values[j-1] + j - 1) > imax:\n",
    "                imax = s\n",
    "            if (s := imax + values[j] - j) > res:\n",
    "                res = s\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        mx = values[0] + 0\r\n",
    "        for j in range(1, len(values)):\r\n",
    "            ans = max(ans, mx + values[j] - j)\r\n",
    "            mx = max(mx, values[j] + j)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        max_pre = values[0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            res = max(res, values[i] - i + max_pre)\n",
    "            max_pre = max(max_pre, values[i] + i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        res = values[0] + values[1] - 1\n",
    "        dp = res\n",
    "        for i in range(2, n):\n",
    "            dp = max(dp + values[i] - values[i-1] - 1, values[i] + values[i-1] -1)\n",
    "            res = max(res, dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans=0\n",
    "        maxValue=0\n",
    "        for i in range(len(values)):\n",
    "            ans=max(ans,maxValue+values[i]-i)\n",
    "            maxValue=max(maxValue,values[i]+i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        mx=values[0]\n",
    "        ans=0\n",
    "        for j in range(1,len(values)):\n",
    "            cur=values[j]-j\n",
    "            ans=max(ans,mx+cur)\n",
    "            mx=max(mx,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, A: List[int]) -> int:\n",
    "        buff=A[0]\n",
    "        ans=0\n",
    "        for j in range(1,len(A)):\n",
    "            buff-=1\n",
    "            ans=max(ans,buff+A[j])\n",
    "            buff=max(buff,A[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        a = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            a -= 1\n",
    "            ans = max(ans,values[i] + a)\n",
    "            a = max(a,values[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # k = values[i]+i + (values[j]-j)\n",
    "        n = len(values)\n",
    "        ans,mx = 0,values[0]+0\n",
    "        for j in range(1,n):\n",
    "            ans = max(ans,mx+values[j]-j)\n",
    "            mx = max(mx,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        a=values[0]+values[1]-1\n",
    "        b=max(values[0],values[1]+1)\n",
    "        for i in range(2,len(values)):\n",
    "            if (s:=b+values[i]-i)>a:\n",
    "                a=s\n",
    "            if (s:=values[i]+i)>b:\n",
    "                b=s\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # j=1,初始化res[1],imax[1]\n",
    "        # score = V[i]+V[j]+i-j\n",
    "        res=values[0]+values[1]+0-1\n",
    "        imax=max(values[0]+0,values[1]+1)\n",
    "        for j in range(2,len(values)):\n",
    "            # walrus operator\n",
    "            if (tmp:=values[j-1]+j-1)>imax:\n",
    "                imax=tmp\n",
    "            if (tmp:=imax+values[j]-j)>res:\n",
    "                res=tmp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        mtv = values[0]\n",
    "        mti = 0\n",
    "        ans = 0\n",
    "        for i in range(1,len(values)):\n",
    "            ans = max(mtv + values[i] - i + mti, ans)\n",
    "            if values[i] > mtv - i + mti:\n",
    "                mtv = values[i]\n",
    "                mti = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = values[0] + 0\n",
    "        \n",
    "        for j in range(1, len(values)):\n",
    "            ans = max(ans, mx + values[j] - j)\n",
    "            # 边遍历边维护\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        premax = values[0] + 0\n",
    "        for j in range(1, len(values)):\n",
    "            res = max(res, values[j] - j + premax)\n",
    "            premax = max(premax, values[j] + j)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        '''\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if values[i] + values[j] + i - j > ans:\n",
    "                    ans = values[i] + values[j] + i - j\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        maxSightseeingIndex = values[0] + 0\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,maxSightseeingIndex + values[i] - i)\n",
    "            maxSightseeingIndex = max(values[i] + i,maxSightseeingIndex)\n",
    "            #print(ans, maxSightseeingIndex)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        dp = values[0]\n",
    "        ans = 0\n",
    "        for i in range(1,len(values)):\n",
    "            dp -= 1\n",
    "            ans = max(dp + values[i], ans)\n",
    "            if values[i] > dp:\n",
    "                dp = values[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        if len(values) < 2:\n",
    "            return -1\n",
    "        left = values[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, len(values), 1):\n",
    "            ans = max(ans, left + values[i] - i)\n",
    "            left = max(left, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_imax = 0\n",
    "        for j in range(1, len(values)):\n",
    "            pre_imax = max(pre_imax, (values[j-1]+j-1))\n",
    "            res = max(res, pre_imax+values[j]-j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_i = 0\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            ans = max(ans,values[j]-j+max_i)\n",
    "            max_i = max(max_i,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        candidate = values[-1] #= []\n",
    "        res = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            # 先遍历candidates 他是后面可能更高的组合,\n",
    "            # candidates 不用记住值，遍历后直接减1就行了，\n",
    "            # 当前元素加入candidates后 所有小于x的人都不用看了 其实是单调栈吧\n",
    "            # x ... 56 这56是一个地位\n",
    "            \n",
    "            # for j, c in enumerate(candidates):\n",
    "            #     res = max(res, values[i] + candidates[j])\n",
    "            #     candidates[j] -= 1\n",
    "            #     if candidates[i] == 0\n",
    "            candidate -= 1\n",
    "            res = max(res, values[i] + candidate)\n",
    "            candidate = max(candidate, values[i])\n",
    "        return res\n",
    "\n",
    "\n",
    "            # 再过滤candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        values[i] + values[j] + i - j\n",
    "        (values[i] + i) + values[j] - j\n",
    "        维护values[i] + i最大值，枚举答案 max(left + right)\n",
    "    '''\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        for i, x in enumerate(values):\n",
    "            ans = max(ans, left + x - i)\n",
    "            left = max(left, x + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        left = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,values[i] - i + left)\n",
    "            left = max(left,values[i] + i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = [0]*n\n",
    "        mx[0] = values[0]\n",
    "        ans = [0] * n\n",
    "        for j in range(1, n):\n",
    "            mx[j] = max(mx[j-1], values[j] + j)\n",
    "            ans[j] = values[j] - j + mx[j-1]\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        zu = [0]*len(values)\n",
    "        for i in range(len(values)):\n",
    "            zu[i] = values[i]-i \n",
    "        max_index = [0]*len(values)\n",
    "        max_index[-1] = len(values) - 1 \n",
    "        for i in range(len(values)-2,-1,-1):\n",
    "            if zu[i] > zu[max_index[i+1]]:\n",
    "                max_index[i] = i \n",
    "            else:\n",
    "                max_index[i] = max_index[i+1]\n",
    "        res = -inf\n",
    "        for i in range(len(values)-1):\n",
    "            res = max(res,i - max_index[i+1] + values[i] + values[max_index[i+1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #有向边--> pairi到i\n",
    "        #还原，对所选的边进行还原，到也不麻烦，记录节点是否被选即可\n",
    "        #没有很好的还原，这一题对于不同子树的考量并不相同,并不是考虑点，而是考虑边了\n",
    "        n=len(edges)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,(y,_) in enumerate(edges):\n",
    "            if y==-1:continue\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(x:int,fa:int)->(int,int): #选择一条端点起点是x的边，不选择端点起点是x的边      \n",
    "            s1,s2=0,0 #s1代表将x选择\n",
    "            max_diff=-inf\n",
    "            g1,g2=0,0\n",
    "            for y in g[x]:\n",
    "                if y==fa:\n",
    "                    continue\n",
    "                f1,f2=dfs(y,x)\n",
    "                #选择了x，那么y一定不能选\n",
    "                s1=edges[y][1]+f2\n",
    "                s2=max(f1,f2)\n",
    "                max_diff=max(max_diff,s1-s2)\n",
    "                g2+=s2\n",
    "\n",
    "            return g2+max_diff,g2\n",
    "        return max(dfs(0,-1))\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #树上DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            #cur用来保存只选一条边时,最大的差值\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点(向下考虑),那它的孩子节点可以选一个连接,其他不能选。\n",
    "            #dp[1]表示选当前节点(向下考虑),那它的孩子节点一个都不能选\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        dic = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dic[edges[i][0]].append(i)\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not dic[root]:\n",
    "                return edges[root][1],0\n",
    "            sumn = 0\n",
    "            diff = 0\n",
    "            for k,child in enumerate(dic[root]):\n",
    "                tmp1,tmp2 = dfs(child)\n",
    "                sumn+=tmp2\n",
    "                if tmp1-tmp2>diff:\n",
    "                    diff=tmp1-tmp2\n",
    "            res = max(res,edges[root][1]+sumn,sumn+diff)\n",
    "            return edges[root][1]+sumn,sumn+diff\n",
    "        print(dfs(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点\n",
    "            #dp[1]表示选当前节点(向下考虑)\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #树上DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            #cur用来保存只选一条边时,最大的差值\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点(向父节点考虑),那它的孩子节点可以选一个连接,其他不能选。\n",
    "            #dp[1]表示选当前节点(向父节点考虑),那它的孩子节点一个都不能选\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        dic = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dic[edges[i][0]].append(i)\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not dic[root]:\n",
    "                return edges[root][1],0\n",
    "            sumn = 0\n",
    "            diff = 0\n",
    "            for k,child in enumerate(dic[root]):\n",
    "                tmp1,tmp2 = dfs(child)\n",
    "                sumn+=tmp2\n",
    "                if tmp1-tmp2>diff:\n",
    "                    diff=tmp1-tmp2\n",
    "            res = max(res,edges[root][1]+sumn,sumn+diff)\n",
    "            return edges[root][1]+sumn,sumn+diff\n",
    "        print(dfs(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #树上DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            #cur用来保存只选一条边时,最大的差值\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点(向下考虑)\n",
    "            #dp[1]表示选当前节点(向下考虑)\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点\n",
    "            #dp[1]表示选当前节点(向下考虑)\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        n=len(edges)\n",
    "        for i,(p,w) in enumerate(edges):\n",
    "            g[p].append((i,w))\n",
    "        def dfs(k):\n",
    "            rx,rn=0,0#这个点相邻的选了， 这个点相邻的没选\n",
    "            t=[]\n",
    "            for nk,w in g[k]:\n",
    "                x,n=dfs(nk)\n",
    "                t.append((x,n,w))\n",
    "                rn+=x\n",
    "            rx=rn\n",
    "            for x,n,w in t:\n",
    "                rx=max(rx,rn-x+n+w,rn-x+n)\n",
    "            return rx,rn\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        n=len(edges)\n",
    "        for i,(p,w) in enumerate(edges):\n",
    "            g[p].append((i,w))\n",
    "        def dfs(k):\n",
    "            re_use,re_no_use=0,0#这个点相邻的选,这个点相邻的没选\n",
    "            t=[]\n",
    "            for nk,w in g[k]:\n",
    "                u,n=dfs(nk)\n",
    "                t.append((u,n,w))\n",
    "                #累加所有下面的选了的\n",
    "                re_no_use+=u\n",
    "            #初始化选了的值，至少要比都没选的高\n",
    "            re_use=re_no_use\n",
    "            for u,n,w in t:\n",
    "                #枚举选了的话 选那一条边 注意W可能为负数\n",
    "                re_use=max(re_use,re_no_use-u+n+w,re_no_use-u+n)\n",
    "            return re_use,re_no_use\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        n=len(edges)\n",
    "        for i,(p,w) in enumerate(edges):\n",
    "            g[p].append((i,w))\n",
    "        def dfs(k):\n",
    "            re_use,re_no_use=0,0#这个点相邻的选,这个点相邻的没选\n",
    "            t=[]\n",
    "            for nk,w in g[k]:\n",
    "                u,n=dfs(nk)\n",
    "                t.append((u,n,w))\n",
    "                #累加所有下面的选了的\n",
    "                re_no_use+=u\n",
    "            #初始化选了的值，至少要比都没选的高\n",
    "            re_use=re_no_use\n",
    "            for u,n,w in t:\n",
    "                #枚举选了的话 选那一条边 注意W可能为负数\n",
    "                re_use=max(re_use,re_no_use-u+n+w,re_no_use-u+n)\n",
    "            return re_use,re_no_use\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        tree = collections.defaultdict(list)\n",
    "        n = len(edges)\n",
    "        for i in range(1, n):\n",
    "            tree[edges[i][0]].append([i, edges[i][1]])\n",
    "        \n",
    "        def dfs(i):\n",
    "            if not tree[i]:\n",
    "                return 0, 0\n",
    "            \n",
    "            can, cannot = [], []\n",
    "            for nex, val in tree[i]:\n",
    "                nexCan, nexCannot = dfs(nex)\n",
    "                can.append(max(nexCan, nexCannot))\n",
    "                cannot.append(nexCan + val - can[-1])\n",
    "            \n",
    "            ans = sum(can)        \n",
    "            return ans, ans + max(cannot)\n",
    "\n",
    "        can, cannot = dfs(0)\n",
    "        return max(can, cannot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        tree = collections.defaultdict(list)\n",
    "        n = len(edges)\n",
    "        for i in range(1, n):\n",
    "            tree[edges[i][0]].append([i, edges[i][1]])\n",
    "        \n",
    "        def dfs(i):\n",
    "            if not tree[i]:\n",
    "                return 0, 0\n",
    "            \n",
    "            can, cannot = [], []\n",
    "            for nex, val in tree[i]:\n",
    "                nexCan, nexCannot = dfs(nex)\n",
    "                can.append(max(nexCan, nexCannot))\n",
    "                cannot.append(nexCan + val - can[-1])\n",
    "            \n",
    "            ans = sum(can)        \n",
    "            return ans, ans + max(cannot)\n",
    "\n",
    "        can, cannot = dfs(0)\n",
    "        return max(can, cannot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        d = collections.defaultdict(dict)\n",
    "        for u, (v, w) in enumerate(edges):\n",
    "            if u != 0:\n",
    "                d[v][u] = w\n",
    "        \n",
    "        def dfs(u):\n",
    "            if not d[u]:\n",
    "                return 0, 0\n",
    "            w_ans = []\n",
    "            left_ans = []\n",
    "            right_ans = []\n",
    "            for v in d[u]:\n",
    "                w_ans.append(d[u][v])\n",
    "                left_value, right_value = dfs(v)\n",
    "                left_ans.append(left_value)\n",
    "                right_ans.append(right_value)\n",
    "            m = len(w_ans)\n",
    "            sum_left_ans = sum(left_ans)\n",
    "            sum_right_ans = sum(right_ans)\n",
    "            left_output = -float('inf')\n",
    "            right_output = sum_left_ans\n",
    "            for i in range(m):\n",
    "                left_output = max(left_output, w_ans[i] + right_ans[i] + sum_left_ans - left_ans[i])\n",
    "            left_output = max(left_output, right_output)\n",
    "            return left_output, right_output\n",
    "        return dfs(0)[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 树形DP\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        # 多叉树的打家劫舍\n",
    "        # edges[i] = [parenti,weighti]\n",
    "        graph = collections.defaultdict(list) # key == node, val == children\n",
    "        for i, pair in enumerate(edges):\n",
    "            graph[pair[0]].append((i, pair[1]))\n",
    "\n",
    "        # 然后记忆化搜索，要么\n",
    "\n",
    "        @cache\n",
    "        def dfs(node): # 以node为根节点，看可以选择哪些值\n",
    "            maxVal = 0\n",
    "            # 选择了它，则不可以选择它的孩子，但可以选择它的孙子\n",
    "            cs = [0] # 加个哨兵0，防止sum求空列表\n",
    "            for child, weight in graph[node]:\n",
    "                cs.append(dfs(child))\n",
    "\n",
    "            tsum = sum(cs)\n",
    "            maxVal = max(maxVal, tsum) # 注意这里的边界处理，不选择任意一条边，只选择它们的孩子\n",
    "            for i, pair in enumerate(graph[node]):\n",
    "                child, weight = pair\n",
    "                g = 0 # 考虑它的孙子辈的总和\n",
    "                for grandson, w2 in graph[child]:\n",
    "                    g += dfs(grandson)      \n",
    "\n",
    "                maxVal = max(maxVal, weight + tsum - dfs(child) + g) # 总和减去不可选择的这条孩子的和\n",
    "\n",
    "            return maxVal \n",
    "        \n",
    "\n",
    "        return dfs(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (a, b) in enumerate(edges[1:], 1):\n",
    "            g[a].append([i, b])\n",
    "\n",
    "        @cache\n",
    "        def f(node):\n",
    "            if not g[node]:\n",
    "                return 0, 0\n",
    "            a, b = 0, 0\n",
    "            res = 0\n",
    "            for nxt, w in g[node]:\n",
    "                res += max(f(nxt)[0], f(nxt)[1])\n",
    "            for nxt, w in g[node]:\n",
    "                b = max(b, res - max(f(nxt)[0], f(nxt)[1]) + w + f(nxt)[0])\n",
    "            return res, b \n",
    "        \n",
    "        return max(f(0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        tree = [[] for _ in range(len(edges))]\n",
    "\n",
    "        for u, (fa, w) in enumerate(edges):\n",
    "            if fa == -1: continue\n",
    "            tree[fa].append((u, w))\n",
    "        \n",
    "        @cache\n",
    "        def treeDP(u, op):\n",
    "            dp0 = dp1 = 0\n",
    "            for v, w in tree[u]: dp1 += treeDP(v, 0)\n",
    "            if op: return dp1\n",
    "            for v, w in tree[u]: dp0 = max(dp0, dp1 - treeDP(v, 0) + treeDP(v, 1) + w)\n",
    "            return max(dp0, dp1)\n",
    "        \n",
    "        return treeDP(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\r\n",
    "        n = len(edges)\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for i, [fa, w] in enumerate(edges):\r\n",
    "            if i == 0: continue\r\n",
    "            g[fa].append((i, w))\r\n",
    "            \r\n",
    "        @cache\r\n",
    "        def dfs(u, state):\r\n",
    "            # 叶子结点没有子节点 返回0\r\n",
    "            if not g[u]:\r\n",
    "                return 0\r\n",
    "            ans = res = 0\r\n",
    "            # 假如一条边都不选\r\n",
    "            for v, w in g[u]:\r\n",
    "                ans += dfs(v, False)\r\n",
    "            # 当前点已经被选过了，所以儿子一个都不能选\r\n",
    "            if state: return ans\r\n",
    "            # 当前点没被选中，那只能选一个儿子，并且其他儿子都不选\r\n",
    "            for v, w in g[u]:\r\n",
    "                res = max(res, ans - dfs(v, False) + dfs(v, True) + w)\r\n",
    "            return max(ans, res)\r\n",
    "        return dfs(0, False)\r\n",
    "        \r\n",
    "\r\n",
    "    def maxScore2(self, edges: List[List[int]]) -> int:\r\n",
    "        \"\"\"在树中选择一些边使得选出的边不相连，最大化边权之和\"\"\"\r\n",
    "\r\n",
    "        def dfs(cur: int, pre: int) -> Tuple[int, int]:\r\n",
    "            \"\"\"返回[选择连接父亲的边时子树最大价值, 不选择连接父亲的边时子树最大价值]\r\n",
    "\r\n",
    "            如果选到父亲的边,所有儿子都不能选\r\n",
    "            如果不选到父亲的边,所有儿子中选一个diff最大的\r\n",
    "            \"\"\"\r\n",
    "            res1, res2 = 0, 0\r\n",
    "            diff = [0]\r\n",
    "            for next in adjMap[cur]:\r\n",
    "                select, jump = dfs(next, cur)\r\n",
    "                res1, res2 = res1 + jump, res2 + jump\r\n",
    "                diff.append(select + adjMap[cur][next] - jump)\r\n",
    "\r\n",
    "            res2 += max(diff)\r\n",
    "            return res1, res2\r\n",
    "\r\n",
    "        adjMap = defaultdict(lambda: defaultdict(lambda: -inf))\r\n",
    "        for cur, (parent, weight) in enumerate(edges):\r\n",
    "            if parent == -1:\r\n",
    "                continue\r\n",
    "            adjMap[parent][cur] = weight\r\n",
    "\r\n",
    "        return max(0, dfs(0, -1)[1])  # 不连接虚拟根节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, (x, y) in enumerate(edges):\n",
    "            g[x].append((i, y))\n",
    "        @cache\n",
    "        def f(x, flag):\n",
    "            if flag:\n",
    "                rnt = 0\n",
    "                for y, v in g[x]:\n",
    "                    rnt += f(y, False)\n",
    "            else:\n",
    "                rnt = 0\n",
    "                for y, v in g[x]:\n",
    "                    rnt += f(y, False)\n",
    "                for y, v in g[x]:\n",
    "                    t = v + f(y, True)\n",
    "                    for z, v in g[x]:\n",
    "                        if y != z:\n",
    "                            t += f(z, False)\n",
    "                    rnt = max(rnt, t)\n",
    "            return rnt\n",
    "                        \n",
    "        return f(0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        maxScore = -1\n",
    "        ans = [0] * 12  # Initialize bobArrows with 0 arrows for each position\n",
    "\n",
    "        for i in range(1 << len(aliceArrows)):  # Binary enumeration\n",
    "            score = 0\n",
    "            arrow = 0\n",
    "            bobArrows = [0] * 12\n",
    "\n",
    "            for j, v in enumerate(aliceArrows):\n",
    "                if (i >> j) & 1 == 1:  # Check if Alice used the arrow\n",
    "                    score += j\n",
    "                    arrow += v + 1\n",
    "                    bobArrows[j] = v + 1  # Bob takes one extra arrow\n",
    "\n",
    "            if arrow > numArrows:\n",
    "                continue\n",
    "\n",
    "            if score > maxScore:\n",
    "                maxScore = score\n",
    "                bobArrows[0] += numArrows - arrow  # Fill the first position to reach numArrows\n",
    "                ans = bobArrows[:]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        # 网友的写法\n",
    "        def dfs(remainingArrows,pos,finalScores):\n",
    "            nonlocal maxScore,ans\n",
    "            if pos > 11:\n",
    "                if remainingArrows >= 0 and finalScores > maxScore:\n",
    "                    maxScore = finalScores\n",
    "                    ans = tmp[:]\n",
    "                    ans[0] = remainingArrows\n",
    "                return\n",
    "            tmp[pos] = aliceArrows[pos] + 1\n",
    "            dfs(remainingArrows - aliceArrows[pos] - 1,pos + 1,finalScores + pos)\n",
    "            tmp[pos] = 0\n",
    "            dfs(remainingArrows,pos + 1,finalScores)\n",
    "\n",
    "        tmp = [0 for _ in range(12)]\n",
    "        maxScore = 0\n",
    "        ans = tmp\n",
    "        dfs(numArrows,1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        # 我这个思路没有问题，但是求解的目标错了！\n",
    "        def dfs(pos,curScore,remainingArrows):\n",
    "            nonlocal maxScore,ans\n",
    "            if pos == 12:\n",
    "                if curScore > maxScore:\n",
    "                    maxScore = curScore\n",
    "                    bobArrows[0] += remainingArrows\n",
    "                    ans = bobArrows[:]\n",
    "                    bobArrows[0] -= remainingArrows\n",
    "                return\n",
    "            # 选\n",
    "            if remainingArrows >= aliceArrows[pos] + 1:\n",
    "                remainingArrows -= aliceArrows[pos] + 1\n",
    "                curScore += pos\n",
    "                bobArrows[pos] = aliceArrows[pos] + 1\n",
    "                dfs(pos + 1,curScore,remainingArrows)\n",
    "                bobArrows[pos] = 0\n",
    "                curScore -= pos\n",
    "                remainingArrows += aliceArrows[pos] + 1\n",
    "                dfs(pos + 1,curScore,remainingArrows)\n",
    "            # 不选\n",
    "            else:\n",
    "                dfs(pos + 1,curScore,remainingArrows)\n",
    "\n",
    "        bobArrows = [0] * 12\n",
    "        maxScore = 0\n",
    "        ans = bobArrows\n",
    "        dfs(0,0,numArrows)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if k == 1:\n",
    "            return max(cardPoints[0], cardPoints[-1])\n",
    "        n = len(cardPoints)\n",
    "        if k == n:\n",
    "            return sum(cardPoints)\n",
    "        # if k == n-1:\n",
    "        #     return sum(cardPoints) - min(cardPoints)\n",
    "        #滑动窗口 找连续n-k个数字的最小值，用总和相减\n",
    "        m = sum(cardPoints)\n",
    "        window = n-k\n",
    "        cur_res = sum(cardPoints[:window])\n",
    "        res = cur_res\n",
    "        for i in range(window, n):\n",
    "            cur_res = cur_res + cardPoints[i]-cardPoints[i-window]\n",
    "            res = min(res, cur_res) \n",
    "        return m-res\n",
    "\n",
    "        #用dfs会超时"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 转变思路，求最小点数\n",
    "        n = len(cardPoints)\n",
    "        total = sum(cardPoints)\n",
    "        if n == k:\n",
    "            return total\n",
    "        \n",
    "        sum_, min_sum = 0, float('inf')\n",
    "        start = 0\n",
    "        m = n - k  # 窗口长度最大值\n",
    "\n",
    "        for end in range(n):\n",
    "            sum_ += cardPoints[end]\n",
    "\n",
    "            if end >= m - 1:\n",
    "                min_sum = min(sum_, min_sum)\n",
    "                sum_ -= cardPoints[start]\n",
    "                start += 1\n",
    "        \n",
    "        return total - min_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n=len(cardPoints)\n",
    "        ans,sum=0,0\n",
    "        for i in range(0,k):\n",
    "            sum+=cardPoints[i]\n",
    "        ans=sum  #初始化最大值为从左边取k张牌\n",
    "        l,r=k-1,n-1\n",
    "        while l>=0:\n",
    "            sum-=cardPoints[l]\n",
    "            sum+=cardPoints[r]\n",
    "            ans=max(ans,sum)\n",
    "            l-=1\n",
    "            r-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n=len(cardPoints)\n",
    "        window_size=n-k\n",
    "        tmp=sum(cardPoints[:window_size])\n",
    "        min_sum=tmp\n",
    "        for i in range(window_size,n):\n",
    "            tmp=tmp+cardPoints[i]-cardPoints[i-window_size]\n",
    "            min_sum=min(min_sum,tmp)\n",
    "        return sum(cardPoints)-min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        total = sum(cardPoints)\n",
    "        sums = sum(cardPoints[ : n - k])\n",
    "        minimum = sums\n",
    "        for i in range(1, k + 1):\n",
    "            sums = sums - cardPoints[i - 1] + cardPoints[n - k + i - 1]\n",
    "            if sums < minimum :\n",
    "                minimum = sums\n",
    "        return total - minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        total = sum(cardPoints)\n",
    "        w_sum = sum(cardPoints[:n-k])\n",
    "        res = total - w_sum\n",
    "        for i in range(n-k,n):\n",
    "            w_sum = w_sum - cardPoints[i-n+k] + cardPoints[i]\n",
    "            res = max(res, total - w_sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        start = sum(cardPoints[:n-k])\n",
    "        res = start\n",
    "        for i in range(n-k, n):\n",
    "            start = start - cardPoints[i-n+k] + cardPoints[i]\n",
    "            res = min(start, res)\n",
    "        return sum(cardPoints) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        len_ = n - k\n",
    "        sum_ = 0\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            sum_ +=cardPoints[i] # 总和 \n",
    "        # 找k个数最大，就是找n-k个数最小\n",
    "        for i in range(len_):\n",
    "            cur += cardPoints[i] \n",
    "        min_ = cur \n",
    "        for i in range(len_, n):\n",
    "            cur = cur + cardPoints[i] - cardPoints[i-len_]\n",
    "            min_ = min(min_, cur)\n",
    "        return sum_ - min_\n",
    "# 宫水三叶的解法，配合负雪明烛的动图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        # 滑动窗口大小为 n-k\n",
    "        windowSize = n - k\n",
    "        # 选前 n-k 个作为初始值\n",
    "        s = sum(cardPoints[:windowSize])\n",
    "        minSum = s\n",
    "        for i in range(windowSize, n):\n",
    "            # 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值\n",
    "            s += cardPoints[i] - cardPoints[i - windowSize]\n",
    "            minSum = min(minSum, s)\n",
    "        return sum(cardPoints) - minSum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        \n",
    "        #取左边的+右边的 为最大值的话，可以考虑为：取中间连续子数组的和为最小值。\n",
    "       #因为左右取K个，则替换为，取len-k 个值，使其和最小。\n",
    "        length = len(cardPoints)\n",
    "        left = 0\n",
    "        right = length - k -1\n",
    "        sum_value = sum(cardPoints[left:right+1])\n",
    "        min_value = sum_value\n",
    "        while right < length:\n",
    "            left+=1\n",
    "            right+=1\n",
    "            if right >= length:\n",
    "                break\n",
    "            sum_value = sum_value + cardPoints[right] - cardPoints[left-1]\n",
    "            min_value = min(sum_value,min_value)\n",
    "        return sum(cardPoints) - min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxScore(self, cardPoints, k):\n",
    "        n = len(cardPoints)\n",
    "        sums = sum(cardPoints)\n",
    "        k = n - k\n",
    "        ans = float('inf')\n",
    "        sum_k = 0\n",
    "\n",
    "        for i, x in enumerate(cardPoints):\n",
    "            sum_k += x\n",
    "\n",
    "            if i >= k :\n",
    "                sum_k -= cardPoints[i - k]\n",
    "            if i >= k-1:\n",
    "                ans = min(ans, sum_k)\n",
    "\n",
    "        return sums - ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        sum_ = 0\n",
    "        max_score = 0\n",
    "        start = -k\n",
    "        for end in range(-k, k):\n",
    "            sum_ += cardPoints[end]\n",
    "            if max_score < sum_:\n",
    "                max_score = sum_\n",
    "            if end >= -1:\n",
    "                sum_ -= cardPoints[start]\n",
    "                start += 1\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        total_sum = sum(cardPoints)\n",
    "        m = len(cardPoints) - k\n",
    "        cur = sum(cardPoints[:m])\n",
    "        min_v = cur\n",
    "        for i in range(m, len(cardPoints)):\n",
    "            cur = cur + cardPoints[i] - cardPoints[i - m]\n",
    "            min_v = min(min_v, cur)\n",
    "        return total_sum - min_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, arr: List[int], k: int) -> int:\n",
    "        size = len(arr)-k\n",
    "        cur = 0\n",
    "        ttl = sum(arr)\n",
    "        res = ttl \n",
    "        l,r = 0,0\n",
    "        if size==0:\n",
    "            return ttl \n",
    "        while r<len(arr):\n",
    "            cur += arr[r]\n",
    "            if r-l+1>=size:\n",
    "                res = min(res,cur)\n",
    "                cur -= arr[l]\n",
    "                l+=1\n",
    "            r += 1\n",
    "        return ttl - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        \n",
    "        m = len(cardPoints)-k\n",
    "        if m==0:\n",
    "            return sum(cardPoints)\n",
    "        l,r,res,cur = 0,0,float('inf'),0\n",
    "        while r<len(cardPoints):\n",
    "            cur += cardPoints[r]\n",
    "            if r-l+1>=m:\n",
    "                res = min(res,cur)\n",
    "                cur-=cardPoints[l]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return sum(cardPoints)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "\n",
    "        total = sum(cardPoints)\n",
    "        print(total)\n",
    "\n",
    "        cur_sum = sum(cardPoints[0:len(cardPoints)-k])\n",
    "        min_sum = cur_sum\n",
    "\n",
    "        for i in range(0, k):\n",
    "            cur_sum = cur_sum + cardPoints[i+len(cardPoints)-k]-cardPoints[i]\n",
    "            min_sum = min(min_sum, cur_sum)\n",
    "\n",
    "        return total - min_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        start = sum(cardPoints[:n-k])\n",
    "        res = start\n",
    "        for i in range(n-k, n):\n",
    "            start = start - cardPoints[i-n+k] + cardPoints[i]\n",
    "            res = min(res, start)\n",
    "        return sum(cardPoints) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        #前后缀\n",
    "        n = len(cardPoints)\n",
    "\n",
    "        ans = inf\n",
    "\n",
    "        sums = 0\n",
    "        cumu = 0\n",
    "\n",
    "        for j in range(n):\n",
    "            sums += cardPoints[j]\n",
    "            cumu += cardPoints[j]\n",
    "            if j >= n - k:\n",
    "                cumu -= cardPoints[j - (n - k)]\n",
    "            if j >= n - k - 1:\n",
    "                #if j == 3:\n",
    "                #    print(\"hahaha:, \", cumu)\n",
    "                ans = min(ans, cumu)\n",
    "        #print(sums, cumu)\n",
    "        return sums - ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 拿n-k张牌最小\n",
    "\n",
    "        n = len(cardPoints)\n",
    "\n",
    "\n",
    "        pre_sum = sum(cardPoints[0:n-k])\n",
    "        res = pre_sum\n",
    "        left = 0\n",
    "        for right in range(n-k,n):\n",
    "            pre_sum += cardPoints[right]-cardPoints[left]\n",
    "            res = min(res,pre_sum)\n",
    "            left += 1\n",
    "\n",
    "        return sum(cardPoints)-res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        current = sum(cardPoints[:k])\n",
    "        maxpoint = current\n",
    "\n",
    "        for i in range(k-1,-1,-1):\n",
    "            current -=cardPoints[i]\n",
    "            current+=cardPoints[i-k]\n",
    "            # print(i,cardPoints[i],cardPoints[i-k])\n",
    "            if current>maxpoint:\n",
    "                maxpoint = current\n",
    "        return maxpoint\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        #换位思考：求出数组的最小len（cardPoints）-k\n",
    "        window=len(cardPoints)-k\n",
    "        right,left=0,0\n",
    "        min_card=math.inf\n",
    "        tmp_card=0\n",
    "        for right,x in enumerate(cardPoints):\n",
    "            tmp_card+=x\n",
    "            if right - left +1 ==window:\n",
    "                min_card=min(min_card, tmp_card)\n",
    "            if right -left +1 > window:\n",
    "                tmp_card-=cardPoints[left]\n",
    "                left+=1\n",
    "                min_card=min(min_card, tmp_card)\n",
    "        return sum(cardPoints) - min_card"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 拿n-k张牌最小\n",
    "\n",
    "        n = len(cardPoints)\n",
    "        window_size = n - k\n",
    "\n",
    "        sum_count = sum(cardPoints[:window_size])\n",
    "        min_number = sum_count\n",
    "        for i in range(window_size, n):\n",
    "            sum_count = sum_count + cardPoints[i] - cardPoints[i - window_size]\n",
    "            min_number = min(min_number,sum_count)\n",
    "        return sum(cardPoints) - min_number\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        res = max(sum(cardPoints[:k]), sum(cardPoints[len(cardPoints)-k:]))\n",
    "        l, r = k - 1, len(cardPoints)-1\n",
    "        left_sum, right_sum = sum(cardPoints[:l+1]), 0\n",
    "        while l >= 0:\n",
    "            left_sum -= cardPoints[l]\n",
    "            right_sum += cardPoints[r]\n",
    "            res = max(res, left_sum+right_sum)\n",
    "            l -= 1\n",
    "            r -= 1\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\r\n",
    "        n = len(cardPoints)\r\n",
    "        if k == n:\r\n",
    "            return(sum(cardPoints))\r\n",
    "\r\n",
    "        cur_sum = min_val = cur = sum(cardPoints[:(n - k)])\r\n",
    "        # 连续n - k个数的最小值\r\n",
    "        for i in range(n - k, n):\r\n",
    "            cur_sum += cardPoints[i]\r\n",
    "            cur += (cardPoints[i] - cardPoints[i - (n - k)])\r\n",
    "            min_val = min(min_val, cur)\r\n",
    "        return(cur_sum - min_val)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        if k == len(cardPoints):\n",
    "            return sum(cardPoints)\n",
    "        sum_, min_sum = 0, float(\"inf\")\n",
    "        m = len(cardPoints) - k\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(cardPoints)):\n",
    "            sum_ += cardPoints[end]\n",
    "            if end >= m - 1:\n",
    "                min_sum = min(min_sum, sum_)\n",
    "                sum_ -= cardPoints[start]\n",
    "                start += 1\n",
    "        return sum(cardPoints) - min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        res = sum(cardPoints[-k:])\n",
    "        tmp = sum(cardPoints[-k:])\n",
    "        n = len(cardPoints)\n",
    "        for i in range(n - k, n):\n",
    "            tmp = tmp - cardPoints[i % n] + cardPoints[(i + k) % n]\n",
    "            res = max(res, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        nums=cardPoints[-k:]+cardPoints[:k]\n",
    "        n=len(nums)\n",
    "        left, right=0, k\n",
    "        cur=sum(nums[0:k])\n",
    "        res=cur\n",
    "\n",
    "        for right in range(k, n):\n",
    "            cur+=nums[right]\n",
    "            cur-=nums[left]\n",
    "            left+=1\n",
    "            res=max(res, cur)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        points1=cardPoints[-k:]+cardPoints[:k]\n",
    "        temp=sum(points1[:k])\n",
    "        ans=temp\n",
    "        for i in range(k):\n",
    "            temp-=points1[i]\n",
    "            temp+=points1[i+k]\n",
    "            ans=max(ans,temp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if n <= k:\n",
    "            return sum(cardPoints)\n",
    "        else:\n",
    "            card_0 = cardPoints[::-1]\n",
    "            cardPoints.extend(cardPoints)\n",
    "            m = n - k\n",
    "            len_max = sum(card_0[:k])\n",
    "            len_mid = sum(card_0[:k])\n",
    "            for i in range(m, n):\n",
    "                len_mid = len_mid - cardPoints[i] + cardPoints[i + k]\n",
    "                len_max = max(len_max, len_mid)\n",
    "\n",
    "            return len_max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n=len(cardPoints)\n",
    "        \n",
    "        prefix=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            prefix[i+1]=prefix[i]+cardPoints[i]\n",
    "        #print(prefix)\n",
    "        res=inf\n",
    "        for i in range(k+1):\n",
    "            res=min(res,prefix[n-k+i]-prefix[i])#窗口大小为n-k\n",
    "        return prefix[n]-res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        if k==len(cardPoints):\n",
    "            return sum(cardPoints)\n",
    "        n = len(cardPoints)\n",
    "        temp = sum(cardPoints)\n",
    "        presum = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i]+cardPoints[i]\n",
    "        for i in range(k+1):\n",
    "            temp = min(presum[i+n-k]-presum[i],temp)\n",
    "        return sum(cardPoints)-temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "\n",
    "        length = len(cardPoints)\n",
    "        if k == length: return sum(cardPoints)\n",
    "        width = length - k\n",
    "        l, r,  = 0, 0\n",
    "        idx, total, min_sum = 0, 0, math.inf\n",
    "\n",
    "        while r < length:\n",
    "            right = cardPoints[r]\n",
    "            total += right\n",
    "\n",
    "            if r - l + 1 >= width:\n",
    "                print(\"hello\")\n",
    "                if total < min_sum:\n",
    "                    \n",
    "                    idx = l\n",
    "                    print(\"idx:\", idx)\n",
    "                    min_sum = total\n",
    "                \n",
    "                left = cardPoints[l]\n",
    "                total -= left\n",
    "                l += 1\n",
    "            print(\"total: \", total)\n",
    "            r += 1\n",
    "        print(idx, width)\n",
    "\n",
    "        ans = 0\n",
    "        for i, item in enumerate(cardPoints):\n",
    "            print(i, item)\n",
    "            if idx <= i <= idx + width - 1:\n",
    "                continue\n",
    "            ans += item\n",
    "        return ans\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "\n",
    "#         all_length = len(cardPoints)\n",
    "#         if all_length == k: return sum(cardPoints)\n",
    "        \n",
    "#         sub_length = all_length - k\n",
    "#         l, r, total, ans = 0, 0, 0, math.inf\n",
    "\n",
    "#         for r in range(all_length):\n",
    "#             total += cardPoints[r]\n",
    "#             while r - l + 1 >= sub_length:\n",
    "#                 ans = min(ans, total)\n",
    "#                 total -= cardPoints[l]\n",
    "#                 l += 1 \n",
    "        \n",
    "#         return sum(cardPoints) - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if k >= n:\n",
    "            return sum(cardPoints)\n",
    "        \n",
    "        a = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            a[i] = a[i - 1] + cardPoints[i - 1]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            b[i] = b[i + 1] + cardPoints[i]\n",
    "            \n",
    "        # print(a, b)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            # print(i, a[i], b[n+ i - k])\n",
    "            res = max(res, a[i] + b[n + i - k])\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        pre = [0] * n\n",
    "        pre[0] = cardPoints[0]\n",
    "        temp = pre[0]\n",
    "        for i in range(1, n):\n",
    "            temp += cardPoints[i]\n",
    "            pre[i] = temp\n",
    "        suf = [0] * n\n",
    "        suf[0] = cardPoints[-1]\n",
    "        temp = suf[0]\n",
    "        for j in range(1, n):\n",
    "            temp += cardPoints[n - j -1]\n",
    "            suf[j] = temp\n",
    "        ans = max(pre[k-1], suf[k-1])\n",
    "        for i in range(k-1):\n",
    "            ans = max(ans, pre[i] + suf[k-i-2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        m = len(cardPoints)\n",
    "        score = [0] * (k+1)\n",
    "        rScore = [0] * (k+1)\n",
    "        for i in range(1, k+1):\n",
    "            score[i] = score[i - 1] + cardPoints[i - 1]\n",
    "            rScore[k - i] = rScore[k + 1 - i] + cardPoints[m - i]\n",
    "        score = [x+y for x,y in zip(score,rScore)]\n",
    "\n",
    "        return max(score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        new_cards = cardPoints[-k:]\n",
    "        new_cards.extend(cardPoints)\n",
    "        max_sum = sum(new_cards[:k])\n",
    "        now_sum = max_sum\n",
    "        for i in range(k, min(len(new_cards), 2 * k)):\n",
    "            now_sum = now_sum + new_cards[i] - new_cards[i - k]\n",
    "            max_sum = max(max_sum, now_sum)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        card_size = n-k\n",
    "        pre_sum = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre_sum[i] = pre_sum[i-1]+cardPoints[i-1]\n",
    "        sum_all = pre_sum[n]\n",
    "        seleted_card = pre_sum[card_size]\n",
    "        \n",
    "        for i in range(n-card_size+1):\n",
    "            #print(cardPoints[i:i+card_size])\n",
    "            seleted_card = min(seleted_card,pre_sum[i+card_size]-pre_sum[i])\n",
    "\n",
    "        return sum_all-seleted_card"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if n == 1:\n",
    "            return cardPoints[0]\n",
    "        if n == k:\n",
    "            return sum(cardPoints)\n",
    "        seq_sum, rev_sum = [cardPoints[0]] * n, [cardPoints[-1]] * n\n",
    "        for i in range(1, n):\n",
    "            seq_sum[i] = cardPoints[i] + seq_sum[i-1]\n",
    "            rev_sum[n-i-1] = cardPoints[n-i-1] + rev_sum[n-i]\n",
    "        max_score = max(seq_sum[k-1], rev_sum[n-k])\n",
    "        for i in range(k-1):\n",
    "            if max_score < seq_sum[i] + rev_sum[n-k+i+1]:\n",
    "                max_score = seq_sum[i] + rev_sum[n-k+i+1]\n",
    "        return max_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        pre_sum, suf_sum = [0], [0]\n",
    "        for i in range(len(cardPoints)):\n",
    "            pre_sum.append(pre_sum[-1]+cardPoints[i])\n",
    "            suf_sum.append(suf_sum[-1]+cardPoints[len(cardPoints)-i-1])\n",
    "        max_ = 0\n",
    "        for i in range(k+1):\n",
    "            max_ = max(max_, pre_sum[i] + suf_sum[k-i])\n",
    "        return max_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        list1 = []\n",
    "        n = len(cardPoints)\n",
    "        if k == n:\n",
    "            return sum(cardPoints)\n",
    "        else:\n",
    "            list1.extend(cardPoints[k-1::-1])\n",
    "            list1.extend(cardPoints[:n-k-1:-1])\n",
    "            print(list1)\n",
    "            max_count = sum(list1[:k])\n",
    "            count = max_count\n",
    "            for i in range(k, 2*k):\n",
    "                count += list1[i]\n",
    "                count -= list1[i-k]\n",
    "                # count = sum(list1[i:i+k])\n",
    "                max_count = max(max_count, count)\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        sums = [0]\n",
    "        for i in cardPoints:\n",
    "            sums.append(sums[-1]+i)\n",
    "        n = len(cardPoints)\n",
    "        res = 0\n",
    "        for i in range(k+1):\n",
    "            res = max(res, sums[-1]-(sums[i+(n-k)]-sums[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        presum = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i]+cardPoints[i]\n",
    "        ans = inf\n",
    "        size = n-k\n",
    "        for i in range(k+1):\n",
    "            ans = min(ans,presum[i+size]-presum[i])\n",
    "        return presum[-1]-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        a = 0\n",
    "        arr = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            a += cardPoints[i]\n",
    "            arr[i+1] = a\n",
    "        ans = 0\n",
    "        for i in range(k+1):\n",
    "            ans = max(ans,arr[i]+arr[-1]-arr[n-k+i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        prefsum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefsum[i] = prefsum[i-1] + cardPoints[i-1]\n",
    "        # 左边抽i张，右边抽k-i张\n",
    "        min_points = float('inf')\n",
    "        for i in range(k + 1):\n",
    "            min_points = min(min_points, prefsum[n - k + i] - prefsum[i])\n",
    "\n",
    "        return prefsum[n] - min_points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        pre_sum = list(accumulate(cardPoints, initial=0))\n",
    "        res = 0\n",
    "        for i in range(k+1):\n",
    "            res = max(res, pre_sum[i]+pre_sum[-1]-pre_sum[-k+i-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxScore(self, cardPoints, k):\n",
    "        \"\"\"\n",
    "        :type cardPoints: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(cardPoints)\n",
    "        preSum = [0] * (N + 1)\n",
    "        for i in range(N):\n",
    "            preSum[i + 1] = preSum[i] + cardPoints[i]\n",
    "        res = float(\"inf\")\n",
    "        windowSize = N - k\n",
    "        for i in range(k + 1):\n",
    "            res = min(res, preSum[windowSize + i] - preSum[i])\n",
    "        return preSum[N] - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # pre_sum = list(accumulate(cardPoints, initial=0))\n",
    "        # res = 0\n",
    "        # for i in range(k+1):\n",
    "        #     res = max(res, pre_sum[i]+pre_sum[-1]-pre_sum[-k+i-1])\n",
    "        # return res\n",
    "\n",
    "        # ----------------------------\n",
    "        n = len(cardPoints)\n",
    "        pre_sum = list(accumulate(cardPoints, initial=0))\n",
    "        min_val = inf\n",
    "        for i in range(k+1):\n",
    "            min_val = min(min_val, pre_sum[i+n-k]-pre_sum[i])\n",
    "        return pre_sum[-1] - min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def maxScore(self,cardPoints,k):\n",
    "        n = len(cardPoints)\n",
    "        preSum = [0] * (n + 1)\n",
    "        windows_size = n - k\n",
    "        res = float(\"inf\")\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + cardPoints[i]\n",
    "        #窗口尺寸\n",
    "        for j in range(k + 1):\n",
    "            res = min(preSum[windows_size + j]-preSum[j],res)\n",
    "        max_points = sum(cardPoints) - res\n",
    "        return max_points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "- 前缀和问题\n",
    "- 类似题目Leetcode 1658 Minimum Operations to Reduce X to Zero\n",
    "- 问题变换为 大小为n-k的连续子数组之和最小\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        preSum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + cardPoints[i]\n",
    "        \n",
    "        delta = n - k\n",
    "        minSum = inf\n",
    "        for i in range(k+1):\n",
    "            # print(preSum[i+delta] - preSum[i])\n",
    "            minSum = min(minSum, preSum[i+delta] - preSum[i])\n",
    "    \n",
    "        if minSum == inf:\n",
    "            minSum = 0\n",
    "        return preSum[-1] - minSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + cardPoints[i]\n",
    "        \n",
    "        res = float('inf')\n",
    "        windowSize = n - k\n",
    "        for i in range(k+1):\n",
    "            res = min(res,pre[windowSize + i] - pre[i])\n",
    "        #抽走的卡牌点数之和 = cardPoints 所有元素之和 - 剩余的中间部分元素之和\n",
    "        return pre[n] - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        suml = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            suml[i+1] = suml[i] + cardPoints[i]\n",
    "        ans = - suml[-1]\n",
    "        for i in range(k+1):\n",
    "            ans = max(suml[i] - suml[-k+i-1],ans)\n",
    "        return ans + suml[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        presum = [0]*(n+1)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            presum[i] = cardPoints[i-1] + presum[i-1]\n",
    "\n",
    "        for i in range(k+1): # i from left, k-i from right\n",
    "            cur_res = presum[i]+presum[n]-presum[n-k+i]\n",
    "            res = max(cur_res, res)  \n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        N=len(cardPoints)\n",
    "        preSum=[0]*(N+1)\n",
    "        for i in range(N):\n",
    "            preSum[i+1]=preSum[i]+cardPoints[i]\n",
    "        res=float(\"inf\")\n",
    "        windowSize=N-k\n",
    "        for i in range(k+1):\n",
    "            res=min(res,preSum[windowSize+i]-preSum[i])\n",
    "        return preSum[N]-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        sums = [0]\n",
    "        for i in cardPoints:\n",
    "            sums.append(sums[-1]+i)\n",
    "        n = len(cardPoints)\n",
    "        res = 0\n",
    "        for i in range(k+1):\n",
    "            res = max(res, sums[-1]-(sums[i+(n-k)]-sums[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        forward = [0] * (n+1)\n",
    "        backward = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            forward[i] = forward[i-1] + cardPoints[i-1]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            backward[i] = backward[i+1] + cardPoints[i]\n",
    "        ans = 0\n",
    "        l, r = 0, n-1\n",
    "        while k > 0:\n",
    "            if (forward[l+k] - forward[l]) >= (backward[r-k+1]-backward[r+1]):\n",
    "                ans += cardPoints[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                ans += cardPoints[r]\n",
    "                r -= 1\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        minpoints,n = float(inf),len(cardPoints)\n",
    "        precardsum = [0]*(n+1)\n",
    "        # precardsum[0] = cardPoints[0]\n",
    "        for i in range(1,n+1):\n",
    "            precardsum[i] = precardsum[i-1] + cardPoints[i-1]\n",
    "        size = n-k\n",
    "        for j in range(k+1):\n",
    "            # print('precardsum[n-j]:',precardsum[n-j])\n",
    "            # print('precardsum[size-j]:',precardsum[size-j])\n",
    "            minpoints = min(minpoints,precardsum[size+j]-precardsum[j])\n",
    "        # print('minpoints:',minpoints)\n",
    "        # print('precardsum:',precardsum)\n",
    "        # print('minpoints:',minpoints)\n",
    "        return precardsum[n]-minpoints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # @cache\n",
    "        # def process(i, j, rest):\n",
    "        #     if rest == 0:\n",
    "        #         return 0\n",
    "\n",
    "        #     return max(cardPoints[i]+process(i+1, j, rest-1), cardPoints[j]+process(i, j-1, rest-1))\n",
    "\n",
    "        # return process(0, len(cardPoints)-1, k)\n",
    "\n",
    "        from itertools import accumulate\n",
    "        preSum = list(accumulate(cardPoints))\n",
    "        preSum.insert(0, 0)\n",
    "        ans = float('inf')\n",
    "        for i in range(k+1):\n",
    "            ans = min(ans, preSum[i+len(cardPoints)-k]-preSum[i])\n",
    "        return preSum[-1] - ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        pre = list(accumulate(cardPoints, initial = 0))\n",
    "        n = len(cardPoints)\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            o = k - i\n",
    "            f = pre[i] - pre[0]\n",
    "            e = pre[-1] - pre[n - o]\n",
    "            res = max(res, f + e)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        res = sum(cardPoints[:n-k]) # 第一个大小为n-k的滑动窗口的元素和\n",
    "        preSum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + cardPoints[i]\n",
    "        for i in range(k+1):\n",
    "            res = min(res, preSum[n-k+i] - preSum[i])\n",
    "        # for i in range(k+1):\n",
    "        #     res = min(res, sum(cardPoints[i: n-k+i]))\n",
    "\n",
    "        # print(sum(cardPoints))\n",
    "        return sum(cardPoints) - res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # @cache\n",
    "        # def process(i, j, rest):\n",
    "        #     if rest == 0:\n",
    "        #         return 0\n",
    "\n",
    "        #     return max(cardPoints[i]+process(i+1, j, rest-1), cardPoints[j]+process(i, j-1, rest-1))\n",
    "\n",
    "        # return process(0, len(cardPoints)-1, k)\n",
    "\n",
    "        from itertools import accumulate\n",
    "        preSum = list(accumulate(cardPoints))\n",
    "        preSum.insert(0, 0)\n",
    "        ans = float('inf')\n",
    "        for i in range(k+1):\n",
    "            ans = min(ans, preSum[i+len(cardPoints)-k]-preSum[i])\n",
    "        return preSum[-1] - ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 正难则反\n",
    "        # 两边拿k个最大 也就是中间去掉n-k\n",
    "        # 要求n-k加起来最小\n",
    "        # 直接用滑动窗口去做\n",
    "        n = len(cardPoints)\n",
    "        m = n - k\n",
    "        ans = sum(cardPoints[0:m])\n",
    "        nums = [ans]\n",
    "        if n == k:\n",
    "            return sum(cardPoints)\n",
    "        for i in range(k):\n",
    "            print(cardPoints[i], cardPoints[i+m])\n",
    "            temp = ans - cardPoints[i] + cardPoints[i+m]\n",
    "            nums.append(temp)\n",
    "            ans = temp\n",
    "        print(f\"nums: {nums}\")\n",
    "        return sum(cardPoints) - min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        temp = []\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        count = 0\n",
    "        N = len(cardPoints)\n",
    "        if k >= len(cardPoints):\n",
    "            return sum(cardPoints)\n",
    "        for i in range(k):\n",
    "            temp.append(cardPoints[i])\n",
    "        for i in range(k):    \n",
    "            temp.insert(0, cardPoints[N-1-i])\n",
    "        print(temp)\n",
    "        M = len(temp)\n",
    "        start = 0 \n",
    "        end = 0\n",
    "        while end < M:\n",
    "            cur += temp[end]\n",
    "            count += 1\n",
    "            if count == k:\n",
    "                res = max(res, cur)\n",
    "                cur -= temp[start]\n",
    "                count -= 1\n",
    "                start += 1\n",
    "            end += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        pre = list(accumulate(cardPoints, initial=0))\n",
    "        ans = -inf\n",
    "        n = len(cardPoints)\n",
    "        for x in range(k+1):\n",
    "            left = pre[x]\n",
    "            right = pre[-1] - pre[n-k+x]\n",
    "            if left + right > ans:\n",
    "                ans = left+right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        pre = [0 for _ in range(len(cardPoints)+1)]\n",
    "        post = [0 for _ in range(len(cardPoints)+1)]\n",
    "   \n",
    "        for i in range(1, len(cardPoints)+1):\n",
    "            pre[i] = pre[i-1] + cardPoints[i-1]\n",
    "            post[i] = post[i-1] + cardPoints[-i]\n",
    "\n",
    "        mx = 0 \n",
    "        for i in range(k+1):\n",
    "            mx = max(mx, pre[i] + post[k-i])\n",
    "\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 前缀后缀和\n",
    "        pre_sum,suf_sum = [0],[0]\n",
    "        t = 0\n",
    "        for i in range(len(cardPoints)):\n",
    "            t += cardPoints[i]\n",
    "            pre_sum.append(t)\n",
    "        t = 0\n",
    "        for i in range(len(cardPoints) - 1,-1,-1):\n",
    "            t += cardPoints[i]\n",
    "            suf_sum.append(t)\n",
    "\n",
    "        # 枚举左侧分割点\n",
    "        ans = 0\n",
    "        for i in range(k + 1):\n",
    "            ans = max(ans,pre_sum[i] + suf_sum[k - i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        s,n = sum(cardPoints), len(cardPoints)\n",
    "        forward, backward = [0], [s]\n",
    "        for i in range(n):\n",
    "            forward.append(forward[-1]+cardPoints[i])\n",
    "            backward.append(backward[-1]-cardPoints[i])\n",
    "        res = 0\n",
    "        for i in range(k+1):\n",
    "            res = max(res, backward[i-k-1]+forward[i])\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if n == k:\n",
    "            return sum(cardPoints)\n",
    "\n",
    "        window = n - k\n",
    "        window_sum = 0\n",
    "        window_min = math.inf\n",
    "        total_sum = 0\n",
    "\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            total_sum += cardPoints[right]\n",
    "            window_sum += cardPoints[right]\n",
    "            \n",
    "            if right >= window - 1:\n",
    "                window_min = min(window_min, window_sum)\n",
    "                window_sum -= cardPoints[left]\n",
    "                left += 1\n",
    "            \n",
    "        return total_sum - window_min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        preSum = [0] * (len(cardPoints) + 1)\n",
    "        postSum = [0] * (len(cardPoints) + 1)\n",
    "        for i in range(len(cardPoints)):\n",
    "            preSum[i + 1] = preSum[i] + cardPoints[i]\n",
    "            postSum[i + 1] = postSum[i] + cardPoints[-1 - i]\n",
    "        ans = 0\n",
    "        for i in range(k + 1):\n",
    "            ans = max(ans, preSum[i] + postSum[k - i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if n == k:\n",
    "            return sum(cardPoints)\n",
    "        \n",
    "        sum_, min_sum = 0, math.inf\n",
    "        start = 0\n",
    "        for end in range(n):\n",
    "            sum_ += cardPoints[end]\n",
    "\n",
    "            if end-start+1 == n-k:\n",
    "                min_sum = min(min_sum, sum_)\n",
    "\n",
    "            if end + 1 >= n-k:\n",
    "                sum_ -= cardPoints[start]\n",
    "                start += 1\n",
    "\n",
    "        return sum(cardPoints) - min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        total_sum = sum(cardPoints)\n",
    "        res = total_sum\n",
    "        n = len(cardPoints)\n",
    "        m = n - k\n",
    "        for i in range(len(cardPoints) - m + 1):\n",
    "            sub_list = cardPoints[i : i + m]\n",
    "            res = min(res, sum(sub_list))\n",
    "        return total_sum - res\n",
    "\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        total = sum(cardPoints)\n",
    "        n = len(cardPoints)\n",
    "        res = total\n",
    "        win_sum = 0\n",
    "        left, right = 0, 0\n",
    "        while right < n:\n",
    "            c = cardPoints[right]\n",
    "            right += 1\n",
    "            win_sum += c\n",
    "\n",
    "            while right - left == n - k:\n",
    "                res = min(res, win_sum)\n",
    "\n",
    "                d = cardPoints[left]\n",
    "                left += 1\n",
    "                win_sum -= d\n",
    "\n",
    "        return total - res if total != res else total\n",
    "\n",
    "    def maxScore(self, cardPoints, k):\n",
    "        \"\"\"\n",
    "        :type cardPoints: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(cardPoints)\n",
    "        windowSize = N - k # 窗口的大小\n",
    "        sums = 0\n",
    "        res = float(\"inf\") # 正无穷大\n",
    "        for i in range(N):\n",
    "            sums += cardPoints[i]\n",
    "            if i >= windowSize:\n",
    "                sums -= cardPoints[i - windowSize]\n",
    "            if i >= windowSize - 1:\n",
    "                res = min(res, sums)\n",
    "        return sum(cardPoints) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if n == k:\n",
    "            return sum(cardPoints)\n",
    "\n",
    "        window = n - k\n",
    "        window_sum = 0\n",
    "        window_min = math.inf\n",
    "        total_sum = 0\n",
    "\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            total_sum += cardPoints[right]\n",
    "            window_sum += cardPoints[right]\n",
    "            \n",
    "            if right >= window - 1:\n",
    "                window_min = min(window_min, window_sum)\n",
    "                window_sum -= cardPoints[left]\n",
    "                left += 1\n",
    "            \n",
    "        return total_sum - window_min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if n <= k: return sum(cardPoints)\n",
    "\n",
    "        # window = deque(cardPoints[:k][::-1])\n",
    "        # res = acc = sum(window)\n",
    "        # for i in reversed(range(n - k, n)):\n",
    "        #     acc -= window.popleft()\n",
    "        #     acc += cardPoints[i]\n",
    "        #     window.append(cardPoints[i])\n",
    "        #     if acc > res: res = acc \n",
    "        # return res\n",
    "\n",
    "        res = acc = sum(cardPoints[:k])\n",
    "        j = k - 1\n",
    "        for i in reversed(range(n - k, n)):\n",
    "            acc -= cardPoints[j]\n",
    "            j -= 1\n",
    "            acc += cardPoints[i]\n",
    "            if acc > res: res = acc \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 首先是考虑一下特例看看\n",
    "        n = len(cardPoints)\n",
    "        if k == n:\n",
    "            return sum(cardPoints)\n",
    "        # 换一个想法想 把整个数字减去最小和，且子串长度为m=n-k，那么剩下的就是符合要求的最大值\n",
    "        # 维护变量初始化\n",
    "        m = n-k\n",
    "        score, min_score = 0, math.inf\n",
    "        # 从前往后从后往前是一样的\n",
    "        start = 0\n",
    "        for end in range(len(cardPoints)):\n",
    "            score+=cardPoints[end]\n",
    "            \n",
    "            if end>=m-1:\n",
    "                min_score = min(min_score, score)\n",
    "                score -= cardPoints[start]\n",
    "                start+=1\n",
    "        #print(min_score)\n",
    "        return sum(cardPoints) - min_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        # 滑动窗口\n",
    "        # 求连续 n - k 个数使得其和最小，因为数组整体和不变\n",
    "        tmp = 0\n",
    "        n = len(cardPoints)\n",
    "        total = 0\n",
    "        for i in cardPoints:\n",
    "            total += i\n",
    "        if k == n:return total\n",
    "        for i in range(n - k):\n",
    "            tmp += cardPoints[i]\n",
    "        ans = tmp\n",
    "        for i in range(1,k+1):\n",
    "            j = n - k + i - 1\n",
    "            tmp = tmp + cardPoints[j] - cardPoints[i-1]\n",
    "            ans = min(ans, tmp)\n",
    "        return total - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        a = cardPoints+cardPoints\n",
    "        a1 = len(cardPoints)-k\n",
    "        a2 = len(cardPoints)-1\n",
    "\n",
    "        r=0\n",
    "        for j in cardPoints[len(cardPoints)-k:len(cardPoints)]:\n",
    "            r+=j\n",
    "        re = r\n",
    "        for i in range(k): \n",
    "            tmp1 = a[a1]\n",
    "            a1+=1\n",
    "            a2+=1\n",
    "            tmp2 = a[a2]    \n",
    "            r +=  (tmp2-tmp1)\n",
    "            re = max(re,r)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        length = n - k\n",
    "        l, r = 0, n - k -1\n",
    "        tmp = sum(cardPoints[:n-k])\n",
    "        max_val = tmp\n",
    "        while r < n:\n",
    "            if r + 1 < n:\n",
    "                tmp -= cardPoints[l]\n",
    "                tmp += cardPoints[r+1]\n",
    "                max_val = min(max_val, tmp)\n",
    "            l += 1\n",
    "            r += 1\n",
    "        \n",
    "        sum_all = sum(cardPoints)\n",
    "        return sum_all - max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        #on 20230807\n",
    "        left_sum, right_sum = [0], [0]\n",
    "        for i in range(k):\n",
    "            left_sum.append(cardPoints[i] + left_sum[i])\n",
    "            right_sum.append(cardPoints[-(i+1)] + right_sum[i])\n",
    "        max_sum = 0\n",
    "        for i in range(k+1):\n",
    "            max_sum = max(left_sum[i] + right_sum[k-i], max_sum)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        n = len(cardPoints)\n",
    "        if k >= n:\n",
    "            return sum(cardPoints)\n",
    "        l = 0\n",
    "        res = float(\"inf\")\n",
    "        _sum = 0\n",
    "        _size = len(cardPoints) - k\n",
    "        for r in range(n):\n",
    "            _sum += cardPoints[r]\n",
    "            if r-l+1 > _size:\n",
    "                _sum -= cardPoints[l]\n",
    "                l += 1\n",
    "            if r-l+1 == _size:\n",
    "                res = min(res, _sum)\n",
    "        return sum(cardPoints) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, cardPoints: List[int], k: int) -> int:\n",
    "        nums = cardPoints + cardPoints\n",
    "        n = len(cardPoints)\n",
    "        start = n - k\n",
    "        tmp = sum(nums[start: start+k])\n",
    "        result = tmp\n",
    "        for i in range(start+1, n+1):\n",
    "            tmp = tmp - nums[i-1] + nums[i+k-1]\n",
    "            result = max(result, tmp)\n",
    "        return result\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
